package 数组;

/**
 * 下一个排序
 *
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * 必须 原地 修改，只允许使用额外常数空间。
 */

public class L31_ {

    public static void main(String[] args) {
        int[] ints = {1, 2, 3};
        new L31_().nextPermutation(ints);
        for (int i : ints) {
            System.out.println(i);
        }
    }

    /**
     * 解题思路：
     *      题目有三个问题需要解决：1、如何找到下一个排列， 2、不存在下一个排列的时候如何生成最小的排列， 3、如何原地修改
     *      一、下⼀个排列是找到⼀个⼤于当前排序的字典序，且变⼤的幅度最⼩。那么只能将较⼩的数与较⼤数做⼀次原地交换。
     *         并且较小的数要尽量靠右，较大数也要尽可能的小。原地交换以后，还需要将较⼤数右边的数按照升序重新排列。
     *      二、不存在下一个排列直接数组调转
     *      三、原地交换后对后面的数组进行调转就行
     *
     * 注意：因为排序跨度要尽量的小，故思路要从右边开始遍历，而不是左边
     */
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
/*
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-leetcode-solution/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
}
